#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <iostream>
using namespace std;
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int now = maxWidth;
        vector<string> ans;
        vector<string> temp;

        for (string word : words)
        {
            if (now + 1 > word.size())
            {
                temp.push_back(word);
                now -= (word.size() + 1);
            }
            else
            {
                now += temp.size();
                string kg = getKg(now / (temp.size() - 1 > 0 ? temp.size() - 1 : 1));
                string strz = temp[0];
                int tt = now % (temp.size() - 1 > 0 ? temp.size() - 1 : 1);
                for (int i = 1; i < temp.size(); i++)
                {
                    if (i <= tt)strz += " ";
                    strz += kg + temp[i];
                }
                strz += getKg(maxWidth - strz.size());
                ans.push_back(strz);
                now = maxWidth;
                temp.clear();
                temp.push_back(word);
                now -= (word.size() + 1);
            }
        }
        string strz = temp[0];
        for (int i = 1; i < temp.size(); i++)
        {
            strz += " " + temp[i];
        }
        strz += getKg(maxWidth - strz.size());
        ans.push_back(strz);
        return ans;

    }
    string getKg(int n)
    {
        if (n <= 0)return "";
        string ans = "";
        while (n--)ans += " ";
        return ans;
    }
};